1. Field of the Invention
The present invention generally relates to Computer Aided Design (CAD) and Computer Aided Manufacturing (CAM) systems and, more particularly, to a new method for constructing the Minkowski sums and any derivative morphological transformations of arbitrary (2, 3 or more generally n-dimensional) polyhedra by using standard tools (such as unions, intersections, translations, and linear translational sweeps (LTS)) of existent and proposed geometrical modeling systems based on boundary representation. The invention has broad application to three-dimensional modeling of very large scale integrated (VLSI) circuits, their design and fabrication, mechanical assembly, path planning and collision detection for robots, as well as many other applications of CAD/CAM systems and their underlying geometrical modelling systems.
2. Description of the Prior Art
Operations for constructing solids in currently available commercial CAD systems are limited to instantiations of simple parameterized primitive solids, translational and rotational sweeps, extrusions of two-dimensional cross-sections, rigid motions, and Boolean combinations. Such facilities are insufficient to accommodate many potential CAD/CAM applications. In addition to the automatic generation of engineering drawings and realistic pictures and the analysis of volumetric properties of solid models, the use of CAD systems for planning and simulating manufacturing operations is an essential part of design automation. Experimental systems providing restricted types of bending, twisting, growing, shrinking, rounding, and filleting operations have been publicized. Since these operations typically produce solids bounded by subsets of complicated surfaces, their effects are approximated in terms of the simple surfaces (often restricted to planes) supported by the CAD systems.
Minkowski sums of polyhedra have important applications in CAD/CAM systems. The Minkowski sum of two subsets of n-space, A and B, is defined as EQU A.sym.B={a+b: a.epsilon.A,b.epsilon.B}.
The Minkowski sum (and derivative operations) or equivalent formulations have been considered in various contexts, such as in mathematical morphology, in robotic path planning, in offsetting operations, and in certain manufacturing applications, including the simulation of process steps in integrated circuit fabrication.
The Minkowski difference of A and B, is defined as EQU A.crclbar.B=(A.sup.c .crclbar.B).sup.c,
where A.sup.c denotes the complement of the set A, and the reflection with respect to the origin of A is defined as EQU A'={-a: a.epsilon.A].
In mathematical morphology, the Minkowski sum, the Minkowski difference and the reflection are taken as primitive operations. In terms of these primitives, other powerful morphological transformations with wide applicability to modelling are defined. For example, the erosion of A by B is defined as EQU A.crclbar.B',
and the opening of A with respect to B is defined as EQU (A.crclbar.B').sym.B,
which corresponds to removing the narrow slivers and smoothing small protuberances of A and rounding the convex edges of A in a manner controlled by the shape of B.
FIG. 1 is an example of two polyhedra, 1 and 2 in three-space for which the polyhedron 1 is to be opened by the polyhedron 2. FIG. 2 is the result of the opening of polyhedron 1 with respect to polyhedron 2 for the two polyhedra in FIG. 1.
The published work in this area is rich, very general, and varied; however, the emphasis in the field has been on analytical and algebraic results or in general discussions of applications, especially in the areas of computer vision and porosity analysis. Although, in addition to the simple calculations of reflections and complements, only the calculation of the Minkowski sum is necessary to enable the use of these results in CAD systems, little, if any, information is available in this area on explicitly how to calculate the Minkowski sum.
In robotics, one of the classical problems is to determine a path for an object from an initial state to a final state while avoiding a set of known obstacles. In its simplest formulation, the path is required to be purely translational; that is, no rotations or other shape transformations are allowed. Generally, this has been attacked by dilating the obstacles in a manner dependent on the shape of the object, defining the free space as the complement of the dilated obstacles, and finding a piece-wise linear path in the free space. The dilation of obstacle A by object B is defined in terms of Minkowski sums as EQU A.sym.B'.
More complex and realistic variants of the problem to moving obstacles and rotating objects with moveable subparts have also been treated by Minkowski sums, generally described in higher (i.e., greater than three) dimensional configuration and configuration/time spaces. However, only for the simplest variant has attention been paid to the actual calculation of the required Minkowski sum. In this situation, an ad hoc method has been described for a two-dimensional polyhedral situation with convex objects and convex obstacles with some indications that the approach could be extended to the three-dimensional convex polyhedral case.
FIG. 3 is a polyhedral approximation of a piano 4 in a polyhedral hall 5. FIG. 4 illustrates the type of calculation not taught in the prior art but for which a solution enabled by means of Minkowski sums is desired. More specifically, FIG. 4 represents the translational free space 6 for the motion of a polyhedral approximation of a piano in the hall. FIG. 5 illustrates an example of a polyhedral approximation of a gripper of a robot 7 in a workcell 8. FIG. 6 illustrates the type of calculation not taught in the prior art but for which a solution enabled by means of Minkowski sums is desired. More specifically, FIG. 6 represents the translational free space 9 for the motion of the polyhedral approximation of the gripper of a robot in the workcell.
The offsetting of one solid object or surface A by another B can be described in terms of the Minkowski sum as the calculation of EQU A.sym.B.
The technique has been applied in rounding and filleting operations, the calculation of cutter paths, and in dimensioning and tolerancing studies. These studies have been limited to the situation in which either A or B is a ball or a sphere in three-space. Some exact solutions have been obtained for simple surfaces, and for more complex surfaces and objects, polyhedral and other approximations have been attempted with mixed results.
Certain manufacturing operations, such as some deposition and etching processes in the fabrication of silicon devices such as integrated circuits, result in uniform addition or subtraction of material at specific regions along a solid's boundary. A large class of such transformations have been adequately modelled by Minkowski sums and differences, which combine the solid to be transformed with another geometric set. For example, to grow a solid A by a given amount k along a specified direction v it suffices to generate the Minkowski sum EQU A.sym.{sv: 0.ltoreq.s.ltoreq.k},
which corresponds to the region swept by A as it linearly moves by the distance k along v. More realistic models of the effect of these or other deposition or etching operations require the Minkowski sum of A with more complicated objects. Often the sharp edges formed by the simple directional deposition or etching model are smoothed by Minkowski sums and derivative calculations involving objects generated by Cumulative Translational Sweeps (CTS). A CTS offsetter is defined by the Minkowski sum of finitely many line segments, so that they are always convex, symmetric polyhedra. Smoothing operations and other applications would be better served by wider choice of polyhedra.
FIG. 7 illustrates an example of a CTS approximation of a sphere, and FIG. 8 is an alternative non-CTS approximation. FIG. 9 is a schematic representation of the result of using the object 11 of FIG. 7 as an offset in an operation for a simulation of a deposition process step in the fabrication of a silicon device. FIG. 10 is a schematic representation of a smoother result of using the object 12 of FIG. 8 as an offset in the same operation which is not available in the prior art. This simulation of a deposition process step in the fabrication of a silicon device is more accurate than that of FIG. 9.
Experimental systems providing restricted types of bending, twisting, growing, shrinking, rounding, and filleting operations have been publicized. Some systems have been proposed to extend the coverage to four or more dimensions with support for many of these operations. Since these operations can produce solids bounded by subsets of complicated surfaces, their effects are often approximated in terms of polyhedra which are supported by all CAD systems. Yet even for the class of polyhedra, except for the trivial cases of translations and linear sweeps along edges, no general support of Minkowski sums has been reported or claimed in commercial, experimental or proposed modeling systems.
The following patent and publications are representative of the prior art:
Jean Serra, in "Introduction to Mathematical Morphology", Computer Vision, Graphics, and Image Processing, 35, pp. 283-305 (1986), shows the use of Minkowski sums in morphological transformations and mathematically develops algebraic and analytic properties of them.
Jean Serra, in Image Analysis and Mathematical Morphology, Academic Press (1982), at pp. 47-48, shows the algebraic properties of dilation and erosion operations on discrete domains such as the pixels of an image.
T. Lozano-Perez and M. Wesley, in "An Algorithm for Planning Collision-free Paths Among Polyhedral Obstacles", Comm. ACM, 22, pp. 560-570 (1979), show how to solve the simplest variant of the path planning algorithm by means of Minkowski sums and describe how to find the Minkowski sum of two convex polyhedra in two-space and suggest extensions to a method in three-space.
J. R. Rossignac and A. A. G. Requicha, in "Offsetting Operations in Solid Modelling", Computer Aided Geom. Design, 3, pp. 129-148 (1986), show a method for the computation of the Minkowski sums of balls and simple full dimensional objects in three-space.
J. R. Rossignac, in "Blending and Offsetting Solid Models", TM 54 Production Automation Project (also Ph.D. Dissertation), University of Rochester, June 1985, shows applications of the previous method to the blending of solids in three-space.
R. T. Farouki, in "The Approximation of Non-degenerate Offset Surfaces", Computer Aided Geom. Design, 3, pp. 15-43 (1985), shows a method for calculating offsets of a B-spline surface, which in certain cases is equivalent to computing the boundary of the Minkowski sum of the surface with a ball.
R. C. Evans, G. Koppelman and V. T. Rajan, in U.S. Pat. No. 4,785,399 for "Growing, Shrinking, and Rounding Polyhedra by Controlled Sweeps", show a method for the computation of the Minkowski sum of a CTS body and a general polyhedron and show how a CTS can be used to modify the shape of a polyhedron for use in modelling.
R. C. Evans, G. Koppelman and V. T. Rajan, in "Shaping Geometric Objects by Cumulative Translational Sweeps", IBM J. Res. Develop., 31, pp. 343-360 (1987), show a method for the computation of the Minkowski sum of a CTS body and a general polyhedron and show how a CTS can be used to modify the shape of a polyhedron for use in modelling process steps in the fabrication of silicon devices.
G. M. Koppelman and M. A. Wesley, in "OYSTER: A Study of integrated Circuits as Three-Dimensional Structures", IBM J. Res. Develop., 27, No. 2, pp. 149-163 (1983), show the application of solid modelling techniques to the simulation of process steps in the fabrication of silicon devices.
The prior art shows the use of Minkowski sums for morphological transformations, the use of Minkowski sums in path planning in two, three and n-space, and the use of Minkowski sums in the calculation of offset bodies and shaping operations for simulation of manufacturing processes. The prior art also shows methods for the computation of the Minkowski sums of pairs of convex polyhedral bodies in two-space and suggests methods for pairs of convex polyhedra in three-space, methods for the computation of the Minkowski sum of a ball or sphere with a restricted class of solid bodies or surfaces in three-space, and a method for the computation in three-space of the Minkowski sum of a polyhedron and a body which is a member of a restricted class of bounded, convex, symmetric polyhedra, namely the CTS bodies.
The prior art, however, fails to show or suggest methods or techniques for the computation of the Minkowski sum of two general polyhedra in n-space, methods or techniques for the computation of the Minkowski sum of a full dimensional polyhedron and a general polyhedron, or methods or techniques for the computation of the Minkowski sum of a general convex polyhedron and a general polyhedron. Even in three-space, the prior art fails to show or suggest methods or techniques with these capabilities.
Moreover, the prior art neither shows nor does it suggest the reduction of the problem of the computation of the Minkowski sum of two general polyhedra in n-space to the computation of the Minkowski sums of transversal cells, the computation of the Minkowski sum of a pair of transversal cells by a generalization of linear translational sweeps, or the advantages of treating only pairs of strongly transversal cells. Nor does the prior art teach the method of reducing the complexity of the computation of the Minkowski sum of a full dimensional polyhedron and a general polyhedron to the computation of the Minkowski sum of pairs of transversal (or strongly transversal) cells, the sum of whose dimensions is full, or the method of reducing the complexity of the computation of the Minkowski sum of a general convex polyhedron and a general polyhedron by the use of surrogates. Finally, the prior art neither shows nor suggests that each and every one of these capabilities can be supported by the standard tools and their generalizations in n-space or that in three-space tools sufficient to support these capabilities exist in the underlying geometrical modelling systems of most existent and proposed CAD/CAM systems.